package com.leet.code.simple_array;

/**
 * @description:    1299.将每个元素替换为右侧最大元素
 * @author: WYG
 * @time: 2020/12/30 17:07
 */

public class ReplaceElements {

    public int[] fast_replaceElements(int[] arr) {
        int[] target = new int[arr.length];
        target[arr.length - 1] = -1;
        int max = arr[arr.length - 1];
        for (int i = arr.length - 2; i >= 0; i--) {
            target[i] = max;
            if(arr[i] > max) {
                max = arr[i];
            }
        }
        return target;
    }

    //从后往前遍历,每次查找最大值替换遍历到的元素
    public int[] replaceElements(int[] arr) {
        int max = -1;
        for (int i = arr.length - 1; i >= 0; i--) {
            int curr = arr[i];
            arr[i] = max;
            max = max > curr ? max : curr;
        }
        return arr;
    }

    //从前往后遍历,每次遍历剩余数组中的最大值
    public int[] old_replaceElements(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int max = 0;
            for (int j = i; j < arr.length; j++) {
                if (arr[j] > max) {
                    max = arr[j];
                }
            }
            arr[i - 1] = max;
        }
        arr[arr.length - 1] = -1;
        return arr;
    }
}
